Multi-threading involves supporting multiple threads of execution. The threads can execute simultaneously (e.g., in environments that provide multiple microprocessors and/or multiple processing cores per microprocessor) or in an interleaved fashion (e.g., in environments in which independent hardware is not available to execute each thread). Threads within the same multi-threaded program execute as part of the same process and share the same resources, including memory (i.e., the threads share the same address space).
Many popular programming languages, like C and C++, were designed prior to the rise in popularity of multi-threading. Accordingly, these languages do not feature built-in support for multi-threading. Instead, libraries have been developed to provide primitives that can be used to support multiple threads.
Applications written in languages that provide support for multiple threads of execution via library-based primitives are susceptible to certain types of memory ordering errors when operating according to a weak memory model. Weak memory models effectively allow different threads to each have a different view of the shared memory space. For example, a thread executing on one processor will access its own address space (e.g., provided in a memory that is associated with the processor on which that thread is executing). The thread's address space represents the shared memory (e.g., it is updated in response to the execution of other threads); however, at any point in time, the thread's address space may significantly differ from the address space used by another thread, despite the fact that the threads are technically sharing memory. For example, at time T1, one thread's address space may reflect that the value of variable A is 20, while another thread's address space may reflect that the value of variable A is 0, despite that fact that both threads are part of the same process. Each thread's address space evolves over time (e.g., as values are written to and read from that address space); however, with a weak memory model, there are few constraints on when the different addresses spaces evolve relative to each other.
As an example of a situation in which a memory order error can arise, one thread can include a first instruction that produces a value that is consumed by a second instruction in another thread, yet there may not be any restriction (either in the program or in the memory model) on when the first and second instructions execute relative to each other, and when the results of such execution will be reflected in the shared memory space, as seen by all threads. Accordingly, depending upon when the two instructions execute (or when the shared memory space, as viewed by each thread, is updated based upon the execution of those instructions), the value consumed by the second instruction may or may not depend upon the value produced by the first instruction. If the program's author intended for a dependency to exist, but the instructions can execute in an order that does not reflect that dependency (or vice versa), a memory order error may arise during execution. Memory ordering errors like this are often extremely difficult to detect, since different execution environments and/or compilers can lead to instructions executing (or appearing to execute, from the perspective of each thread) in different orders, such that the memory order error may only arise in certain situations. Accordingly, techniques that facilitate the detection of memory order errors in such environments are desirable.